package edu.kit.aifb.lidasora.ppmModel;

import edu.kit.aifb.lidasora.ppmModel.transitionCount.TransitionCount;

/**
 * A PPM model for context dependent prediction
 * 
 * This is a Prediction by Partial Match (PPM) model for prediction. The
 * predictions are made based on a Markov assumption. PPM models provide several
 * Markov chains of different order. Each layer of PPM model represents an
 * additional order; the n-th layer represents the n-1th order markov model. For
 * further details, see papers on PPM as for example Palpanas.
 * 
 * 
 * @author Daniel Schuh
 * @version 1.0
 * 
 * @param <T>
 *            The objects that should be stored inside the PPM model
 */
public class PPMModel<T> {

	private final int maxDepth;

	private final ModelNode<T> rootNode;

	/**
	 * Create a new PPM model with maxDepth and a default rootCode
	 * 
	 * Create a new PPM model with maxDepth and a default rootCode. The rootCode
	 * has to be != null otherwise you will get an Exception. The rootCode is
	 * not farther important, it just has to guarantee that the root node is
	 * identifiable among the other nodes.
	 * 
	 * @param maxDepth
	 *            the maximum depth of the PPM model
	 * @param rootCode
	 *            a dummy element for root; must not be null
	 * @param tc a counter variable
	 */
	public PPMModel(int maxDepth, T rootCode, TransitionCount tc) {
		this.maxDepth = maxDepth;
		this.rootNode = new ModelNode<T>(null, rootCode, tc.clone());
	}

	/**
	 * Learn a sequence of T-objects
	 * 
	 * Learn a sequence of T-objects. The oldest element has to be the first
	 * argument (or, in case of an array at pos. lenght-1), the youngest element
	 * has to be the last argument (or at pos. 0 in an array). The method adds
	 * every subsequence to maximum length <code> maxDepth</code> to the tree
	 * that is contained in array. Note that the procedure may crash if any of
	 * the arguments are null.
	 * 
	 * @param seq
	 *            Element at pos. 0 is the oldest element, element at pos. 1 is
	 *            younger than 0, etc.
	 */
	public void learnSequence(T... seq) {
		/*
		 * 3 cases: seq = empty, seq < maxdepth and seq > maxdepth
		 */

		if (seq != null) {
			if (seq.length > maxDepth) {
				/*
				 * starting at first position, insert sequences of length
				 * maxDepth into model as long as there is at least one part of
				 * sequence that is long enough for insertion
				 */
				for (int i = 0; i < (seq.length - maxDepth); i++) {
					insertSingleSequence(i, i + maxDepth, seq);
				}
				/*
				 * we now arrived at the end and have to insert the rest, ending
				 * at the length of the seq
				 */
				for (int i = seq.length - maxDepth; i < seq.length; i++) {
					insertSingleSequence(i, seq.length, seq);
				}
			} else {
				// no sequence longer than max. model length
				for (int i = 0; i < seq.length; i++) {
					insertSingleSequence(i, seq.length, seq);
				}
			}
		}
	}

	/**
	 * Inserts a part of the sequence from [startIndex, endIndex) to model
	 * 
	 * Inserts a part of the sequence into model. The part starts at startIndex
	 * (included) and goes to endIndex(excluded). To get a textual
	 * representation of this model, uncomment System.out.println.
	 */
	private void insertSingleSequence(int startIndex, int endIndex, T... seq) {
		ModelNode<T> currNode = rootNode;

		for (int i = startIndex; i < endIndex; i++) {
			currNode.addChild(seq[i]);
			currNode = currNode.getChild(seq[i]);
			// System.out.print("\t" + currNode.toString() +
			// currNode.getCount());
		}
		// System.out.println();
	}

	/**
	 * Returns an array with statistical data of nodes that follow the last one
	 * of the predecessors
	 * 
	 * Returns an array that contains all statistical data about the child nodes
	 * of one node in predecessors. First, it is tried to use the maximum length
	 * of predecessors, but if that would lead to an empty prediction, the
	 * sequence is shortened until a T is found with at least one children. The
	 * first node is the one that is farthest back in history, the last one the
	 * newest; the prediction will make the prediction for this node. The method
	 * also uses predecessors to learn itself afterwards.
	 * 
	 * @param predecessors
	 *            the list of predecessors
	 * @return an array containing information about the children of the
	 *         predecessors
	 */
	public DataSet<T>[] predict(T[] predecessors) {

		if (predecessors == null) {
			return null;
		}

		int startIndex = predecessors.length > maxDepth ? predecessors.length
				- maxDepth : 0;

		ModelNode<T> currentNode = this.rootNode;

		/*
		 * find the node that is already in the model and has the longest chain
		 * of predecessors and children. Start each time one position later. If a 
		 * traversal was successfully completed, leave outer loop
		 * 
		 */
		boolean traversedComplete = false;
		for(int i = 0; i < predecessors.length && !traversedComplete; i++){
			
			traversedComplete = true;
			//Starting at different start positions
			for(int j = i; j <predecessors.length && traversedComplete; j++) {
				if (currentNode.hasChild(predecessors[j])){
					currentNode = currentNode.getChild(predecessors[j]);
				} else {
					traversedComplete = false;
				}
			}
		}

		
		// now, the currentNode contains the last node of the sequence and we
		// have to get its children's node data
		@SuppressWarnings("unchecked")
		DataSet<T>[] result = new DataSet[currentNode.getNumberOfChildren()];
		int i = 0;
		if (result.length > 0) {
			for (ModelNode<T> node : currentNode.children.values()) {
				result[i] = new DataSet<T>(node);
				i++;
			}
		}
		// Finally, insert new sequence
		this.insertSingleSequence(startIndex, predecessors.length, predecessors);
		return result;
	}

	/**
	 * This method updates the model after a false prediction
	 * 
	 * This method updates the model after a false prediction has been made. The
	 * predicted T has to be given as well as the predecessors on which the
	 * prediction has been made. It should be called after each call of predict.
	 * Depending on how strict you want the model to learn, you can either call
	 * this method just for the most probable predicted or for each T that was
	 * not successfully predicted
	 * 
	 * @param predicted
	 *            the node that was predicted (as most probable) from this model
	 * @param predecessors
	 *            the predecessors on which the prediction was made
	 */
	public void predictionFalse(T predicted, T... predecessors) {
		setPrediction(false, predicted, predecessors);
	}

	/**
	 * This method updates the model after a true prediction
	 * 
	 * This method updates the model after a true prediction has been made. The
	 * predicted T has to be given as well as the predecessors on which the
	 * prediction has been made. It should be called after each call of predict.
	 * Depending on how strict you want the model to learn, you can either call
	 * this method just for the most probable predicted or for each T that was
	 * successfully predicted
	 * 
	 * @param predicted
	 *            the node that was predicted (as most probable) from this model
	 * @param predecessors
	 *            the predecessors on which the prediction was made
	 */
	public void predictionTrue(T predicted, T... predecessors) {
		setPrediction(true, predicted, predecessors);
	}

	private void setPrediction(boolean wasSuccessful, T predicted,
			T... predecessors) {

		if (predicted == null || predecessors == null) {
			return;
		}

		int startIndex = predecessors.length > maxDepth ? predecessors.length
				- maxDepth : 0;
		ModelNode<T> currentNode = this.rootNode;
		for (int i = startIndex; i < predecessors.length; i++) {
			if (currentNode.getChild(predecessors[i]) != null)
				currentNode = currentNode.getChild(predecessors[i]);
			else
				break;
		}

		// current Node = last Node before predicted
		if (wasSuccessful) {
			currentNode.getChild(predicted).successfullyPredicted();
		} else {
			currentNode.getChild(predicted).unsuccessfullyPredicted();
		}
	}

	/**
	 * Returns the number of created nodes in this model
	 * 
	 * Returns the number of created nodes in this model
	 * 
	 * @return the number of created nodes in this model
	 */
	public int getCreatedNodesNumber() {
		return ModelNode.nodesCreated;
	}

}
